/*
* 二叉搜索树 binary search tree
*/

#pragma once

#include<assert.h>

template<typename T>
class BstNode
{
public:
	BstNode()
		:left(nullptr), parent(nullptr), right(nullptr) {}
	BstNode(const T& _key)
		:key(_key),left(nullptr),parent(nullptr),right(nullptr) {}

	BstNode<T>* BuyNode(const T& key=0)
	{
		BstNode<T>* newNode = new BstNode<T>(key);
		assert(nullptr != newNode);
		return newNode;
	}
	void FreeNode(BstNode<T>* node)
	{
		delete node;
		node = nullptr;
	}
public:
	T key;
	BstNode* left;
	BstNode* parent;
	BstNode* right;
};

template<typename T>
class BstTree
{
public:
	BstTree();
	~BstTree();

	void InOrder();
	void NoRecInOrder();
	void MirrorNoRecInOrder();

	bool Insert(const T& val);
	bool Delete(const T& val);

	BstNode<T>* FindValue(const T& val);
	BstNode<T>* NoRecFindValue(const T& val);

	int GetSize();
	bool IsEmpty();

private:
	void _InOrder(BstNode<T>* root);
	BstNode<T>* _FindValue(BstNode<T>* root, const T& key);
	BstNode<T>* NextNode(BstNode<T>* node);
	BstNode<T>* PreNode(BstNode<T>* node);

private:
	BstNode<T>* head;
	int cursize;
};